/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: WHY
 * Date: 2023-05-23
 * Time: 21:50
 */
//链表中环的入口节点
public class demo {
    /*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
    public class Solution {

        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            ListNode aNodeInLoop = IsLoop(pHead);
            int numInLoop = 0;
            if(aNodeInLoop == null) {
                return null;
            }
            else {
                numInLoop = NumNodeInLoop(aNodeInLoop);
            }
            ListNode first = pHead;
            ListNode second = pHead;
            while(numInLoop > 0) {
                first = first.next;
                numInLoop--;
            }
            while(first != second){
                first = first.next;
                second = second.next;
            }
            return first;

        }
        //判断是否有环，如果有，返回两个指针相遇的节点，否则返回null
        public ListNode IsLoop(ListNode pHead) {
            if(pHead == null) {
                return null;
            }
            ListNode slow = pHead.next;
            if(slow == null) {
                return null;
            }
            ListNode fast = pHead.next.next;
            if(fast == null) {
                return null;
            }
            while(slow != null && fast != null) {
                if(slow.equals(fast)) {
                    return slow;
                }
                slow = slow.next;
                fast = fast.next;
                if(fast != null) {
                    fast = fast.next;
                }
            }
            return null;
        }

        //环中的节点数目
        public int NumNodeInLoop(ListNode pHead) {
            ListNode temp = pHead.next;
            int res = 1;
            while(temp != pHead) {
                temp = temp.next;
                res++;
            }
            return res;
        }
    }

}
